package com.zx._12_算法.数据结构.bitmap;

/**
 * @version v1.0
 * @Project: knowledge
 * @Title: SimpleBitMap
 * @Description: 简单实现一个bitMa
 *         SimpleBitMap的实现虽然满足要求，但是速度慢，不论使用for循环查找，还是使用indexOf方法，时间复杂度都是O(n)，
 *         加入的元素越多，isExist方法的速度越慢，我们需要一个时间复杂度是O(1)的算法，不论向里面增加了多少数据，
 *         isExist的执行速度都是常量时间。
 *
 *         通过索引操作数据，时间复杂度就是O(1)，题目说明这些数在0到100之间，那么就用每个数自身的值作为索引，
 *         比如对于3这个数，可以让data[3] = 1，就表示把3添加进来了，data[2] = 0，表示2没有添加进来，那么这样一来，
 *         isExist方法就可以利用索引来判断member是否存在。
 * @author: zhangxue
 * @date: 2019年7月31日下午10:43:24
 * @company: 未知之地
 * @Copyright: Copyright (c) 2019
 */
public class SimpleBitMap2 implements BitMap {

    int[] datas = new int[101];

    public static void main(String[] args) {
        int[] datas = {0, 3, 5, 6, 9, 34, 23, 78, 99};
        BitMap bitMap = new SimpleBitMap2();
        for (int i = 0; i < datas.length; i++) {
            bitMap.addMember(datas[i]);
        }

        System.out.println(bitMap.isExist(3));  //true
        System.out.println(bitMap.isExist(7));  //false
        System.out.println(bitMap.isExist(78)); //true
    }

    @Override
    public void addMember(int member) {
        datas[member] = 1;
    }

    /**
     * 时间复杂度= O(1)
     */
    @Override
    public boolean isExist(int member) {
        return datas[member] == 1;
    }
}
